package stack;

import java.util.*;
import java.util.stream.Collectors;

import org.junit.Test;
public class Ex301 {

    @Test 
    public void test() {
        Solution s = new Solution();
        // Solution1 s = new Solution1();

        // System.out.println(s.s);
        List<String> res = s.removeInvalidParentheses("(a)())()");
        System.out.println(res);
    }


    class Solution {
        //BFS方法，需要每删除一个字符进行一次有效性判断
        public List<String> removeInvalidParentheses(String s) {
            List<String> res = new ArrayList<>();
            Set<String> set = new HashSet<>();
            Queue<String> queue = new LinkedList<>();
            queue.offer(s);
            set.add(s);
            String cur, str;
            char c;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (isVaild(cur)) {
                    //如果cur已经合法
                    //res只保留最大的结果
                    int len;
                    if (res.isEmpty() || cur.length() == (len = res.get(0).length())) res.add(cur);
                    else if (cur.length() > len) {
                        res.clear(); //清空小的结果，我猜这种按顺序删除的应该是长度递减的吧
                        res.add(cur);
                    }
                } else {
                    //尝试删除一个字符，并将其放到队列中进行下一轮判断，注意相同的处理结果不需要添加两次
                    for (int i = 0; i < cur.length(); i++) {
                        if ((c = cur.charAt(i)) == '(' || c == ')') {
                            str = new StringBuilder(cur).deleteCharAt(i).toString();
                            if (!set.contains(str)) {
                                //只有删除方案没有，才进行入队
                                set.add(str);
                                queue.offer(str);
                            }
                        }
                    }
                }
            }
            //去重
            set = new HashSet<>(res);
            return new ArrayList<>(set);
        }

        public boolean isVaild(String s) {
            int count = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') count++;
                else if (c == ')' ) {
                    if (--count < 0) return false; //count一旦为0，表示不合法
                }
            }
            return count == 0;
        } 
    }

    //去除无用括号
    class Solution2 {

        /* 
        
            判断是否合法的逻辑：
            维护一个count，遇到( ,count++
            遇到), count--
            任何时候，count < 0意味着不匹配，直接返回
        */
        List<String> res = new ArrayList<>();
        String s;
        public List<String> removeInvalidParentheses(String s) {
            this.s = s;
            int rmleft = 0, rmright = 0, count = 0;
            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (c == '(') {
                    count++;
                } else if (c == ')') {
                    count--;
                }
            }
            if (count > 0) rmleft = count;
            else if (count < 0) rmright = -count;
            dfs(0, 0, new StringBuilder(), rmleft, rmright);
            //去重

            
            return res.stream().collect(Collectors.toSet()).stream().collect(Collectors.toList());
        }

        public void dfs (int idx, int count, StringBuilder sb, int rmleft, int rmright) {
            if (count < 0) return;
            if (idx == s.length()) {
                if (count > 0) return; //count > 0，有额外的左括号，不符合
                if (rmleft != 0 || rmright != 0) return;
                if (res.isEmpty() || res.get(0).length() < sb.length()) {
                    res.clear();
                    res.add(sb.toString());
                } else if (res.get(0).length() == sb.length()) { //与res的最长长度相等，可以直接加入
                    res.add(sb.toString());
                }
                return;
            }
            char c = s.charAt(idx);
            if (c >= 'a' && c <= 'z') {
                //字母必须加入
                sb.append(c);
                dfs(idx + 1, count, sb, rmleft, rmright);
                sb.deleteCharAt(sb.length() - 1);
            } else if (c == '(') {
                //加入左括号
                sb.append('(');
                dfs(idx + 1, count + 1, sb, rmleft - 1, rmright); 
                sb.deleteCharAt(sb.length() - 1);

                //不加入左括号
                dfs(idx + 1, count, sb, rmleft, rmright);
            } else {
                //右括号的情况
                //不加入
                dfs (idx + 1, count, sb, rmleft, rmright);

                if (count - 1 >= 0) {
                    //加入右括号
                    sb.append(')');
                    dfs(idx + 1, count - 1, sb, rmleft, rmright - 1);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }
    //去除无用括号
    class Solution1 {

        /* 
        
            判断是否合法的逻辑：
            维护一个count，遇到( ,count++
            遇到), count--
            任何时候，count < 0意味着不匹配，直接返回
        */
        List<String> res = new ArrayList<>();
        String s;
        public List<String> removeInvalidParentheses(String s) {
            this.s = s;
            dfs(0, 0, new StringBuilder());
            //去重


            return res.stream().collect(Collectors.toSet()).stream().collect(Collectors.toList());
        }

        public void dfs (int idx, int count, StringBuilder sb) {
            if (count < 0) return;
            if (idx == s.length()) {
                if (count > 0) return; //count > 0，有额外的左括号，不符合
                if (res.isEmpty() || res.get(0).length() < sb.length()) {
                    res.clear();
                    res.add(sb.toString());
                } else if (res.get(0).length() == sb.length()) { //与res的最长长度相等，可以直接加入
                    res.add(sb.toString());
                }
                return;
            }
            char c = s.charAt(idx);
            if (c >= 'a' && c <= 'z') {
                //字母必须加入
                sb.append(c);
                dfs(idx + 1, count, sb);
                sb.deleteCharAt(sb.length() - 1);
            } else if (c == '(') {
                //加入左括号
                sb.append('(');
                dfs(idx + 1, count + 1, sb); 
                sb.deleteCharAt(sb.length() - 1);

                //不加入左括号
                dfs(idx + 1, count, sb);
            } else {
                //右括号的情况
                //不加入
                dfs (idx + 1, count, sb);

                if (count - 1 >= 0) {
                    //加入右括号
                    sb.append(')');
                    dfs(idx + 1, count - 1, sb);
                    sb.deleteCharAt(sb.length() - 1);
                }
            }
        }
    }
}
